#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;

const int MAXN = 100010;

vector<int> v[MAXN];
vector<int> v_neg[MAXN]; //通过反图判断终点可以到哪些点

int price[MAXN];
int node[MAXN];

bool vis[MAXN];
bool vis_neg[MAXN];
bool vis_res[MAXN];

int ans = 0;

int x, y, z;
int N, M;

//先利用bfs确定1可以到达的点

void bfs()
{
    queue<int> q;
    q.push(1);
    vis[1] = true;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < v[u].size(); i++)
        {
            int temp = v[u][i];
            if (!vis[temp])
            {
                vis[temp] = true;
                q.push(temp);
            }
        }
    }
    if (!vis[N])
    {
        cout << 0 << endl;
        exit(0);
    }
}

//反图确定能够到达n的点
void bfs_neg()
{
    queue<int> q;
    q.push(N);
    vis_neg[N] = true;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < v_neg[u].size(); i++)
        {
            int temp = v_neg[u][i];
            if (!vis_neg[temp])
            {
                vis_neg[temp] = true;
                q.push(temp);
            }
        }
    }
}

void bfs_res(int x)
{
    queue<int> q;
    q.push(x);
    vis_res[x] = true;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < v[u].size(); i++)
        {
            int temp = v[u][i];
            if (!vis_res[temp])
            {
                if (vis_neg[temp]) //从该点可以到达n
                {
                    ans = max(ans, price[temp] - price[x]);
                }
                vis_res[temp] = true;
                q.push(temp);
            }
        }
    }
}

bool cmp(const int& i,const int& j){
    return price[i]<price[j];
}

int main()
{
    cin >> N >> M;
    if (N == 1)
    {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 1; i <= N; i++)
    {
        cin >> price[i];
        node[i] = i;
    }
    for (int i = 1; i <= M; i++)
    {
        cin >> x >> y >> z;
        v[x].push_back(y);
        v_neg[y].push_back(x);
        if (z == 2)
        {
            v[y].push_back(x);
            v_neg[x].push_back(y);
        }
    }
    bfs();     // 1能到的点
    bfs_neg(); // 能到n的点

    sort(node+1,node+1+N,cmp);

    for (int i = 1; i <= N; i++)
    {
        if (vis[node[i]] && !vis_res[node[i]])
        {
                bfs_res(node[i]);
        }
    }

    cout << ans << endl;

    system("pause");
    return 0;
}